package stack;

import java.util.LinkedList;

public class ValidParenthesisString678 {
    public boolean checkValidString(String s) {
        LinkedList<Integer> stack_left = new LinkedList<>();
        LinkedList<Integer> stack_star = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='('){
                stack_left.push(i);
            }
            if(s.charAt(i)=='*'){
                stack_star.push(i);
            }

            if(s.charAt(i)==')'){
                if(stack_left.size()>0){
                    stack_left.pop();
                }else if(stack_star.size()>0){
                    stack_star.pop();
                }else {
                    return false;
                }
            }
        }

        while (stack_left.size()>0){
            if(stack_star.size()==0){
                return false;
            }
            int leftIndex = stack_left.pop();
            int starIndex = stack_star.pop();
            if(leftIndex>starIndex){
                return false;
            }
        }
        return true;
    }
}
